The present invention relates generally to methods and systems for blending computer generated images and more particularly to methods and apparatus for dehalftoning pixel data stored in a shallow frame buffer.
A computer system can output data to a wide variety of output display devices. Output display devices such as laser printers, plotters, image setters and other printing devices produce an image or "visual representation" onto a sheet of paper, a piece of film or the like, while output display devices such as computer monitors develop visual representations on a computer screen.
Many output display devices receive display data in the form of a pixel map and generate visual representations from the display data. A pixel is a fundamental picture element of a visual representation generated by a display device, and a pixelmap is a data structure including information concerning a number of pixels of the representation.
A printing device prints dots on a piece of paper corresponding to the information in a pixelmap. Alternatively, a computer monitor illuminates pixels based upon the information of a pixelmap. A "raster" output device creates a visual representation by displaying the array of pixels arranged in rows and columns from a pixelmap. Most output devices, other than plotters, are raster output devices.
Printing and visual output devices that produce output in response to page description language input are widely used. A page description language is a high level language for describing objects to be displayed by an output device. An image may be represented and stored in a page description format as a page description language file which includes one or more objects. Generally, a page description language is device independent.
In operation, a conventional printing device configured to process a page description language file interprets the objects within the file and renders the data into pixelmaps to be painted into a frame buffer. Typically, the frame buffer is large enough to store (at least in compressed form) any page that might be printed, and rendered pixelmaps are stored in this buffer. When the entire page has been painted, data stored in the frame buffer may be transferred to a print engine or marking engine for printing. In many devices, rendering may be performed into bands or tiles, instead of into a page-sized frame buffer, to save memory.
Image data stored in the frame buffer may be deep or shallow. The depth refers to the number of bits required to represent a single pixel in the output image. For the purposes of these discussions, a one bit deep frame buffer, referred to as a shallow frame buffer, represents each pixel in an output image with one bit (on or off, where the on and off bit values correspond to the existence or absence of a given color in the output image, typically black or white). Again for the purposes of these discussions a two or more bit deep frame buffer, referred to as a deep frame buffer, represents each pixel in an output image with two or more bits. The actual bit depth of shallow and deep pixel data depends on the specific implementation. The distinction between the two is that shallow pixel data are represented by fewer bits per pixel than are deep pixel data bits and that shallow frame buffer data is created by transforming the deep pixel data (color or gray values). The transformation of deep pixel data into shallow pixel data may be accomplished by numerous methods including halftoning or dithering. For the purposes of these discussions, an example of a halftoning transformation will be described. Those ordinarily skilled in the art will recognize that other transformation techniques are equally well suited to the inventive processes described herein. In a color printer, shallow or deep frame buffers may be used for each color component in an output image. For example, a 1 bit frame buffer in a color printer results in 1 bit per color component for the output image.
Some printing devices such as offset presses and photocopiers include shallow frame buffers for performance reasons and thus are incapable of directly reproducing shades or colors represented by the "deep" data (e.g., shades of gray in a grayscale image or color shades for a color image). Other printing devices include only shallow frame buffers as a cost saving measure. Grayscale or color image data processed and printed on these devices is halftoned in order to provide the appearance of color or shading.
Halftoning is the process of converting color or shade information for a region (the halftone cell) into a pattern of dots that is representative of the shade (or color) of an image in the region. Each halftone cell represents one region of the original image which may include one or more differently shaded sub-regions. A halftone cell consists of a number of device pixels. In a device that produces only black and white pixels, some of the display pixels of each halftone cell are turned black to form regions to represent darker or lighter portions within the cell to correspond to dark and light portions of the original image. In a dark halftone cell, most of the pixels are black, while in a light halftone cell, most of the pixels are white. A complete grid of the original image is composed of many such halftone cells, each of which has an independent density of displayed pixels and therefore a different apparent darkness when viewed from a distance.
A conventional method of selecting which dots to turn black works as follows. For a given halftone cell, the original image is sampled at each device pixel location in the halftone cell to obtain a sample value. This sample value is represented digitally as a number in a fixed range (zero to 255 in an 8 bit system). The sample value is then compared to a threshold value for the particular device pixel location in the halftone cell. The device pixel is turned black if the sample value is greater than the threshold value, and white otherwise.
The threshold values, in turn, are supplied by a threshold array, which provides a threshold value for each pixel in the halftone cell. This process is carried out for each halftone cell of the image. The device plane is tiled with copies of the threshold array, so that each device pixel is mapped to a sample value for a given image and threshold value associated with the particular position in the halftone cell at which the device pixel is located.
A threshold array is much like a sampled image: it is generally a rectangular array of pixel values defined entirely in device space. It can be built algorithmically, by use of a spot function, for example, or it can be built by hand. The sample values occupy some number of bits: in a typical system, the sample values occupy eight bits that represent gray levels ranging from zero for black and 255 for white.
Halftoning is also used to approximate continuous-tone colors by a pattern of pixels using only a limited number of discrete colors. The input to the halftone function includes continuous-tone color components in the device's native color space (deep pixel data). The output includes pixel data representing colors the device can reproduce (shallow pixel data for storage in a shallow frame buffer). Note that in this example, the shallow pixel data may itself be represented by more than one bit per pixel.
Further information on halftoning may be found in U.S. Pat. Nos. 5,235,435, 5,285,291 and 5,305,118 as well as in such standard reference works as Foley, van Dam et al., Computer Graphics, Addison-Wesley (2d ed. 1992), pp. 568-573, and Adobe Systems Incorporated, Adobe PostScript.RTM. Language Reference Manual, Addison-Wesley (2d ed. .COPYRGT.1990), pp. 309-319.
As described above, conventional printing devices may include a raster image processor (RIP). The RIP includes software or firmware that interprets page description language files (a PDL stream) received from a computing system for printing by a print engine.
In a system including a shallow frame buffer, half-toning is used to convert color or shading data for a region (the halftone cell) into an appropriate pattern of black and white (or pattern of primary colors). The pattern thereafter is stored in the shallow frame buffer. As each object in a PDL file is received, the RIP processes the object data and paints the object into the frame buffer.
Transparency is a visual blending effect obtained when a background object (or image) is partially obscured by a foreground object that is drawn over the background object. Numerous other blending effects may be used to integrate foreground and background images. Examples of blending effects include a drop shadow effect, a screen effect, darker and lighter effects and overprinting effects.
However, printing and display systems using halftoning processes cannot simply manipulate shallow pixel data and achieve correct or acceptable blending results. In a halftoning system, the original pixel information associated with a particular color or shade in a region (the halftone cell) is replaced with "halftone" data.
Conventional shallow frame buffer printing devices are unable to reconstruct the original shade or color data from shallow data and accordingly do not support blending effects.